<?php
/**
 * @title 5526. 最多可达成的换楼请求数目 - 闭环
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param Integer $n
     * @param Integer[][] $requests
     * @return Integer
     */
    function maximumRequests($n, $requests) {
        /**
         * @since 2020-09-27 结果
         */
        $result = 0;

        /**
         * @since 2020-09-27 初始化每个楼净出人数, [出, 进, 闭环可能]
         */
        $nums = array_fill(0, $n, []);

        /**
         * @since 2020-09-27 每个人进出
         */
        foreach ($requests as list($out, $in)){
            if($out == $in){
                $result++;
            } else {
                if(isset($nums[$out][$in])){
                    $nums[$out][$in] += 1;
                } else {
                    $nums[$out][$in] = 1;
                }
            }
        }
        // return $result;
        // return $nums;

        /**
         * @since 2020-09-27 找闭环能覆盖最多点
         */
        // return self::find($nums);
        $result += self::find($nums);

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 尝试找闭环
     * @author start2004
     * @since 2020-09-27 Created
     *
     * @param int $to
     * @param int $from
     * @param array $nums
     */
    public function find($nums = []){
        $count = 0;

        /**
         * @since 2020-09-28 找一个可用起点
         */
        foreach ($nums as $num=>$data){
            if(array_sum($data) >= 1){
                $count = self::circle($num, $num, $nums);
                break;
            } else {}
        }

        /**
         * @return
         */
        // echo "count={$count}", str_repeat(PHP_EOL, 2);
        return $count;
    }


    /**
     * @title 尝试找闭环
     * @author start2004
     * @since 2020-09-27 Created
     *
     * @param int $to
     * @param int $from
     * @param array $nums
     */
    public function circle($from = 0, $to = 0, $nums = [], $count = 0, $exists = []){
        $maxCircle = 0;

        /**
         * @since 2020-09-27 尝试所有路线, 找最大环
         */
        if(isset($nums[$from])){
            foreach ($nums[$from] as $dest => $c){
                if($c == 0){
                    continue;
                } else {}

                /**
                 * @since 2020-09-27 避免回溯
                 */
                if(isset($exists[$dest])){
                    continue;
                } else {}

                /**
                 * @since 2020-09-27 扣去这条线
                 */
                $nums[$from][$dest] -= 1;

                /**
                 * @since 2020-09-27 到达目的地
                 */
                if($dest == $to){
                    /**
                     * @since 2020-09-27 剩下是否继续还有闭环
                     */
                    $nextCount = self::find($nums);
                    $currentCount = $count+1 + $nextCount;

                    // echo "to={$to}, count=", $count+1, ", nextCount=", $nextCount, ", maxCircle={$currentCount}", PHP_EOL;
                    // echo "circle={$to}->", implode("->", $exists), "->{$to}", PHP_EOL;
                    // var_dump($nums);
                    // echo str_repeat(PHP_EOL, 3);

                    $maxCircle = max($maxCircle, $currentCount);
                } else {
                    $exists[$dest] = $dest;

                    /**
                     * @since 2020-09-27 继续递归, 是否有解
                     */
                    $currentCount = self::circle($dest, $to, $nums, $count+1, $exists);
                    $maxCircle = max($maxCircle, $currentCount);

                    /**
                     * @since 2020-09-27 还原
                     */
                    unset($exists[$dest]);
                }

                /**
                 * @since 2020-09-27 还原线段
                 */
                $nums[$from][$dest] += 1;
            }
        } else {}

        /**
         * @since 2020-09-28 无解
         */
        if($maxCircle == 0 AND $from == $to){
             unset($nums[$to]);
             $maxCircle = self::find($nums);
        } else {}

        /**
         * @return
         */
        return $maxCircle;
    }
}

/**
 * @url http://127.0.0.1/leetcode/202009/2020.09.27_9.php
 */
$datas = [
    // [5, [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]], // 5
    // [3, [[0,0],[1,2],[2,1]]], // 3
    // [4, [[0,3],[3,1],[1,2],[2,0]]], // 4
    // [3, [[0,0],[1,1],[0,0],[2,0],[2,2],[1,1],[2,1],[0,1],[0,1]]], // 5
    // [3, [[1,2],[0,0],[0,2],[0,1],[0,0],[0,2],[1,0],[0,1],[2,0]]], // 7
    // [3, [[2,2],[2,0],[1,1],[2,1],[1,1],[2,2],[1,0],[0,2],[1,2]]], // 8
    // [3, [[1,2],[1,2],[2,2],[0,2],[2,1],[1,1],[1,2]]], // 4

    // [12, [[0,5],[5,8],[6,2],[2,6],[2,5],[7,6],[0,3],[0,7],[0,1],[8,2]]], // 5
    // [12, [[2,5],[5,8],[8,2],[2,6],[6,2],[7,6]]], // 5

    [20, [[0,11],[1,8],[2,19],[3,10],[6,3],[8,1],[9,5],[9,16],[9,17],[9,18],[10,18],[15,19],[16,9],[17,15],[18,6],[19,9]]], // 12
    // [20, [[1,8],[8,1],[3,10],[10,18],[18,6],[6,3],[9,17],[17,15],[15,19],[19,9],[9,16],[16,9]]], // 12
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->maximumRequests(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
